#define     _CRT_SECURE_NO_DEPRECATE
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

typedef enum { false , true } bool;

/* actions */
typedef enum {
    S,                 /* shift */
    R,                 /* reduce */
    A,                 /* accept */
    E1,                /* error: missing right parenthesis */
    E2,                /* error: missing operator */
    E3,                /* error: unbalanced right parenthesis */
    E4                 /* error: invalid function argument */
} actEnum;

/* tokens */
typedef enum {
    /* operators */
    tAdd,               /* + */
    tSub,               /* - */
    tMul,               /* * */
    tDiv,               /* / */
    tPow,               /* ^ (power) */
    tUmi,               /* - (unary minus) */
    tFact,              /* f(x): factorial */
    tPerm,              /* p(n,r): permutations, n objects, r at a time */
    tComb,              /* c(n,r): combinations, n objects, r at a time */
    tComa,              /* comma */
    tLpr,               /* ( */
    tRpr,               /* ) */
    tEof,               /* end of string */
    tMaxOp,             /* maximum number of operators */
    /* non-operators */
    tVal                /* value */
} tokEnum;

tokEnum tok;            /* token */
double tokval;          /* token value */

#define MAX_OPR         50
#define MAX_VAL         50
char opr[MAX_OPR];      /* operator stack */
double val[MAX_VAL];    /* value stack */
int oprTop, valTop;     /* top of operator, value stack */
bool firsttok;          /* true if first token */

char parseTbl[tMaxOp][tMaxOp] = {
    /* stk      ------------------ input ------------------------ */
    /*         +   -   *   /   ^   M   f   p   c   ,   (   )   $  */
    /*         --  --  --  --  --  --  --  --  --  --  --  --  -- */
    /* + */  { R,  R,  S,  S,  S,  S,  S,  S,  S,  R,  S,  R,  R },
    /* - */  { R,  R,  S,  S,  S,  S,  S,  S,  S,  R,  S,  R,  R },
    /* * */  { R,  R,  R,  R,  S,  S,  S,  S,  S,  R,  S,  R,  R },
    /* / */  { R,  R,  R,  R,  S,  S,  S,  S,  S,  R,  S,  R,  R },
    /* ^ */  { R,  R,  R,  R,  S,  S,  S,  S,  S,  R,  S,  R,  R },
    /* M */  { R,  R,  R,  R,  R,  S,  S,  S,  S,  R,  S,  R,  R },
    /* f */  { R,  R,  R,  R,  R,  R,  R,  R,  R,  R,  S,  R,  R },
    /* p */  { R,  R,  R,  R,  R,  R,  R,  R,  R,  R,  S,  R,  R },
    /* c */  { R,  R,  R,  R,  R,  R,  R,  R,  R,  R,  S,  R,  R },
    /* , */  { R,  R,  R,  R,  R,  R,  R,  R,  R,  R,  R,  R,  E4},
    /* ( */  { S,  S,  S,  S,  S,  S,  S,  S,  S,  S,  S,  S,  E1},
    /* ) */  { R,  R,  R,  R,  R,  R,  E3, E3, E3, R,  E2, R,  R },
    /* $ */  { S,  S,  S,  S,  S,  S,  S,  S,  S,  E4, S,  E3, A }
};

int error(char *msg) {
    printf("error: %s\n", msg);
    return 1;
}

int gettok(void) {
    static char str[82];
    static tokEnum prevtok;
    char *s;

    /* scan for next symbol */
    if (firsttok) {
        firsttok = false;
        prevtok = tEof;
        gets(str);
        if (*str == 'q') exit(0);
        s = strtok(str, " ");
    } else {
        s = strtok(NULL, " ");
    }

    /* convert symbol to token */
    if (s) {
        switch(*s) {
        case '+': tok = tAdd; break;
        case '-': tok = tSub; break;
        case '*': tok = tMul; break;
        case '/': tok = tDiv; break;
        case '^': tok = tPow; break;
        case '(': tok = tLpr; break;
        case ')': tok = tRpr; break;
        case ',': tok = tComa; break;
        case 'f': tok = tFact; break;
        case 'p': tok = tPerm; break;
        case 'c': tok = tComb; break;
        default:
            tokval = atof(s);
            tok = tVal;
            break;
        }
    } else {
        tok = tEof;
    }

    /* check for unary minus */
    if (tok == tSub) {
        if (prevtok != tVal && prevtok != tRpr) {
            tok = tUmi;
        }
    }

    prevtok = tok;
    return 0;
}

int shift(void) {
    if (tok == tVal) {
        if (++valTop >= MAX_VAL) 
            return error("val stack exhausted"); 
        val[valTop] = tokval;
    } else {
        if (++oprTop >= MAX_OPR) return 
            error("opr stack exhausted"); 
        opr[oprTop] = (char)tok;
    }
    if (gettok()) return 1;
    return 0;
}

double fact(double n) {
    double i, t;
    for (t = 1, i = 1; i <= n; i++)
        t *= i;
    return t;
}

int reduce(void) {
    switch(opr[oprTop]) {
    case tAdd:
        /* apply E := E + E */
        if (valTop < 1) return error("syntax error");
        val[valTop-1] = val[valTop-1] + val[valTop];
        valTop--;
        break;
    case tSub:
        /* apply E := E - E */
        if (valTop < 1) return error("syntax error");
        val[valTop-1] = val[valTop-1] - val[valTop];
        valTop--;
        break;
    case tMul:
        /* apply E := E * E */
        if (valTop < 1) return error("syntax error");
        val[valTop-1] = val[valTop-1] * val[valTop];
        valTop--;
        break;
    case tDiv:
        /* apply E := E / E */
        if (valTop < 1) return error("syntax error");
        val[valTop-1] = val[valTop-1] / val[valTop];
        valTop--;
        break;
    case tUmi:
        /* apply E := -E */
        if (valTop < 0) return error("syntax error");
        val[valTop] = -val[valTop];
        break;
    case tPow:
        /* apply E := E ^ E */
        if (valTop < 1) return error("syntax error");
        val[valTop-1] = pow(val[valTop-1], val[valTop]);
        valTop--;
        break;
    case tFact:
        /* apply E := f(E) */
        if (valTop < 0) return error("syntax error");
        val[valTop] = fact(val[valTop]);
        break;
    case tPerm:
        /* apply E := p(N,R) */
        if (valTop < 1) return error("syntax error");
        val[valTop-1] = fact(val[valTop-1])/fact(val[valTop-1]-val[valTop]);
        valTop--;
        break;
    case tComb:
        /* apply E := c(N,R) */
        if (valTop < 1) return error("syntax error");
        val[valTop-1] = fact(val[valTop-1])/
            (fact(val[valTop]) * fact(val[valTop-1]-val[valTop]));
        valTop--;
        break;
    case tRpr:
        /* pop () off stack */
        oprTop--;
        break;
    }
    oprTop--;
    return 0;
}

int parse(void) {

    printf("\nenter expression (q to quit):\n");

    /* initialize for next expression */
    oprTop = 0; valTop = -1;
    opr[oprTop] = tEof;
    firsttok = true;
    if (gettok()) return 1;

    while(1) {

        /* input is value */
        if (tok == tVal) { 
printf("shift value\n");
            /* shift token to value stack */
            if (shift()) return 1;
            continue;
        }

printf("tok=%d, oprTop=%d, opr[OprTop]=%d\n", tok, oprTop, opr[oprTop]);
printf("%d\n", parseTbl[opr[oprTop]][tok]);
        /* input is operator */
        switch(parseTbl[opr[oprTop]][tok]) {
        case R:
printf("reduce\n");
            if (reduce()) return 1;
            break;
        case S:
printf("shift\n");
            if (shift()) return 1;
            break;
        case A:
printf("accept\n");
            /* accept */
            if (valTop != 0) return error("syntax error");
            printf("value = %f\n", val[valTop]);
            return 0;
        case E1:
            return error("missing right parenthesis");
        case E2:
            return error("missing operator");
        case E3:
            return error("unbalanced right parenthesis");
        case E4:
            return error("invalid function argument");
        default:
printf("can't happen!\n");
        }
    }
}

int main(void) {
    while(1) parse();
    return 0;
}
